package genetic.q2;



import java.io.File;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Vector;

public class PuzzleAlgorithm {

	List<PuzzleGenotype> population;
	List<double[]> buildingBlocks;

	int populationSize;
	PuzzlePhenotype prototype;

	double bestFitness = 0;
	int bestGen = 0;
	PuzzleGenotype best = null;

	double BBbestFitness = Integer.MAX_VALUE;
	int BBbestGen = 0;
	double[] bestBB = null;

	public PuzzleAlgorithm(PuzzlePhenotype prototype){
		this.population = new LinkedList<PuzzleGenotype>();
		this.prototype = prototype;
	}

	public void init(int populationSize){
		this.populationSize = populationSize;
		population.clear();
		population = prototype.getInitialPopulation(populationSize);
		bestFitness = Integer.MIN_VALUE;
		buildingBlocks = initializeBB(population);
		bestFitness = Integer.MAX_VALUE;
	}

	public PuzzleGenotype runAlgorithm(int numGenerations, double Pc, double Pm, int elitism, String resultFile){
		PrintWriter out = openFile(resultFile);
		PrintWriter out2 = openFile("bb_"+resultFile);
		double[] initStats = getStatistics(0, true);
		out.println(0 + "\t" + initStats[0] + "\t" + initStats[1]);

		for (int generation=1; generation<=numGenerations; generation++){
			List<PuzzleGenotype> topGun = new LinkedList<PuzzleGenotype>();
			if(elitism!=0)
				topGun = prototype.elitist(population, populationSize, elitism);
			population = prototype.getMatingPool(population, populationSize-elitism);
			List<PuzzleGenotype> newPopulation = new LinkedList<PuzzleGenotype>();
			for (int i=0; i<populationSize-elitism; i+=2){	//breed
				PuzzleGenotype p1 = population.get(i);
				PuzzleGenotype p2 = population.get(i+1);
				PuzzleGenotype[] offsprings;

				double rand = Math.random();
				if (rand<Pc){		//create offsprings
					offsprings = prototype.crossover(p1, p2);
				} else {			//copy parents
					offsprings = new PuzzleGenotype[]{p1.clone(), p2.clone()};
				}

				newPopulation.add(prototype.mutate(offsprings[0], Pm));
				newPopulation.add(prototype.mutate(offsprings[1], Pm));
			}

			for (int i=0; i<topGun.size(); i++){
				newPopulation.add(topGun.get(i));

			}
			population = newPopulation;

			prototype.updateFitness(population);
			evaluateFitnessBB(buildingBlocks, population);		
			updateAidVector(buildingBlocks, population);		
			double[] BBstats = getBBStatistics(generation);
			//	System.out.print("\tBest - " + BBstats[0] + ", Average - " + BBstats[1] + " , Best so far: "+ BBbestFitness+ "\t");

			//	System.out.println();
			out2.println(generation + "\t" + BBstats[0] + "\t" + BBstats[1]);

			buildingBlocks = evolveBB(buildingBlocks, population);
			//	evaluateFitnessBB(buildingBlocks, population);

			double[] stats = getStatistics(generation, true);
			if(generation%10==0)
				System.out.println("Generation "+generation+": Best - " + stats[0] + ", Average - " + stats[1] + " , Best so far: "+ bestFitness+ "\t" + best);
			out.println(generation + "\t" + stats[0] + "\t" + stats[1]);
		}

		System.out.println("Best genotype on final generation, found on generation "+ bestGen+", fitness - "+bestFitness+ ": " + best);
		out.println("Best genotype on final generation, found on generation "+ bestGen+", fitness - "+bestFitness+ ": " + best);
		for(int i=0;i<bestBB.length;i++){
			out2.print("["+bestBB[i]+"]");
		}

		out.close();
		out2.close();

		return best;
	}

	private void evaluateFitnessBB(List<double[]> bb, List<PuzzleGenotype> so  ){
		TSPGenotype g;
		double[] t;
		for(int j=0; j<bb.size(); j++){		
			t=bb.get(j);
			double fit = 0;
			int count=0;
			for(int i=0; i<so.size();i++){
				g = (TSPGenotype)so.get(i);
				double gfit = prototype.fitness(g);
				if(g.travels(t)){
					fit = fit + gfit;
					count++;
				}
			}
			if (count==0)
				fit=Integer.MAX_VALUE;
			else{
				fit = (fit/count);
			}
			t[t.length-1] = fit;
		}		
	}

	private void updateAidVector(List<double[]> bb, List<PuzzleGenotype> so  ){
		TSPGenotype g;
		double[] t;
		for(int i=0; i<so.size();i++){
			g = (TSPGenotype)so.get(i);
			for(int j=0; j<bb.size(); j++){				
				t=bb.get(j);
				if(g.travels(t)){
					g.updateAid(t);
				}
			}
		}		
	}
	private LinkedList<double[]> evolveBB(List<double[]> bb2, List<PuzzleGenotype> so) {
		List<double[]> bb = getBBMatingPoolTournamentSelection(bb2, bb2.size(), 2, 1, 1);
		TSPGenotype g;
		LinkedList<double[]> newbb =new LinkedList<double[]>();
		double[] tmp;
		for(double[] b : bb){
			Random r = new Random();
			double rand= r.nextDouble();
			if(rand<0.8){
				LinkedList<Double> pres = new LinkedList<Double>();
				LinkedList<Double> posts = new LinkedList<Double>();
				for(int i=0; i<so.size();i++){
					g = (TSPGenotype)so.get(i);
					if(g.travels(b)){
						int[] pp =g.getPrePost(b);
						pres.add((double)pp[0]);
						posts.add((double)pp[1]);
					}
				}
				if(r.nextDouble()<0.5){
					if(pres.size()>0){
						int spot= r.nextInt(pres.size());
						tmp = new double[b.length+1];
						tmp[0] = pres.get(spot);
						for(int i=0; i<b.length; i++){
							tmp[i+1]=b[i];
						}					
					}
					else
						tmp = b;
				}else{
					if(posts.size()>0){
						int spot= r.nextInt(posts.size());
						tmp = Arrays.copyOf(b, b.length+1);
						tmp[tmp.length-1]=tmp[tmp.length-2];
						tmp[tmp.length-2]=posts.get(spot);
					}
					else
						tmp=b;
				}
			}else if(rand<0.9){
				tmp = new double[3];
				tmp[0]=(double)r.nextInt(37);
				tmp[1]=(double)r.nextInt(37);
				tmp[2]=Integer.MAX_VALUE;
			}else{
				tmp = b;
			}
			newbb.add(tmp);
		}
		return newbb;
	}

	private List<double[]> initializeBB(List<PuzzleGenotype> so ){
		LinkedList<double[]> bb= new LinkedList<double[]>();
		for(int i=0; i<so.size(); i++){
			int[] rep = so.get(i).getIntString();
			for(int j=0; j<36;j++){	
				double[] tmp = new double[3];
				tmp[0]=rep[j];
				tmp[1]=rep[j+1];
				tmp[2]=Integer.MAX_VALUE;
				if (!inside(bb, tmp))
					bb.add(tmp);
			}
			double[] tmp = new double[3];
			tmp[0]=rep[36];
			tmp[1]=rep[0];
			tmp[2]=Integer.MAX_VALUE;
			if (!inside(bb, tmp))
				bb.add(tmp);
		}
		return bb;
	}

	private boolean inside(LinkedList<double[]> bb, double[] sub) {
		for(int i=0; i<bb.size();i++){
			double[] tmp = bb.get(i);
			if(tmp.length==sub.length){
				int eq=0;
				for(int j=0; j<tmp.length-1;j++){
					if(tmp[j]!=sub[j]){
						break;
					}else eq++;
				}
				if (eq==tmp.length-1)
					return true;
			}
		}
		return false;
	}

	protected List<double[]> getBBMatingPoolTournamentSelection(List<double[]> population, int populationSize, int tournamentSize, int numWinners, double p){
		List<double[]> matingPool = new LinkedList<double[]>();

		while (matingPool.size()<populationSize){
			Vector<double[]> tournament = new Vector<double[]>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}

			Collections.sort(tournament, new Comparator<double[]>(){
				@Override
				public int compare(double[] o1, double[] o2) {
					if (o1[o1.length-1] < o2[o2.length-1]){
						return -1;
					} else if (o1[o1.length-1] > o2[o2.length-1]){
						return 1;
					} else {
						return 0;
					}
				}
			});

			for (int i=0; i<numWinners; i++){
				for (int j=0; j<tournament.size(); j++){
					if (Math.random()<p || j == tournament.size()-1){
						matingPool.add(tournament.remove(j));
						break;
					}
				}
			}
		}
		Collections.shuffle(matingPool);
		return matingPool;
	}


	private double[] getBBStatistics(int gen){
		double BBmaxFitness = Integer.MAX_VALUE;
		double BBaverageFitness = 0;
		double[] BBBest = null;
		for (double[] b: buildingBlocks){
			double fitness = b[b.length-1];
			if(BBmaxFitness > fitness){
				BBmaxFitness = fitness;
				BBBest = b;
			}
			BBaverageFitness = BBaverageFitness + fitness;
		}
		BBaverageFitness = BBaverageFitness/(double)buildingBlocks.size();

		if (BBbestFitness > BBmaxFitness) {
			BBbestFitness = BBmaxFitness;
			bestBB = BBBest;
			BBbestGen = gen;
		}
		return new double[]{ BBmaxFitness, BBaverageFitness};
	}

	private double[] getStatistics(int gen, boolean computeMin){
		double tmpBestFitness = (computeMin ? Integer.MAX_VALUE : Integer.MIN_VALUE);
		double averageFitness = 0;
		PuzzleGenotype genBest = null;
		for (PuzzleGenotype g: population){
			double fitness = prototype.fitness(g);
			if((computeMin && tmpBestFitness > fitness) || (!computeMin && tmpBestFitness < fitness)){
				tmpBestFitness = fitness;
				genBest = g;
			}
			averageFitness = averageFitness + fitness;
		}
		averageFitness = averageFitness/(double)population.size();

		if ((computeMin && bestFitness > tmpBestFitness) || (!computeMin && bestFitness < tmpBestFitness)) {
			bestFitness = tmpBestFitness;
			best = genBest;
			bestGen = gen;
		}
		return new double[]{ tmpBestFitness , averageFitness};
	}

	private PrintWriter openFile(String filename){
		try{
			File f = new File(filename);
			f.delete();
			f.createNewFile();
			PrintWriter out = new PrintWriter(f);
			return out;
		}catch (Exception e) {
			return null;
		}
	}

	public static void main(String[] args) {
		TSPGraph graph = new TSPGraph("TSP1.txt");
		graph.readFile();
		TSPPhenotype p = new TSPPhenotype(graph.getSize(), graph);
		PuzzleAlgorithm ga = new PuzzleAlgorithm(p);
		for (int i=1; i<=10; i++){
			ga.init(100);
			ga.runAlgorithm(750, 0.8, 0.1,0, "r1-"+i+".txt");
		}
	}
}